#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
 
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
链接：https://leetcode.cn/problems/palindrome-partitioning
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
// vector<vector<string>>
//
// 算是 回溯中的分割问题
bool isPalindrome(string &s) {
    if (s.size() == 1)
        return true;


    int low = 0;

    int high = s.size() - 1;
    while (low <= high) {

        if (s[low++] != s[high--])
            return false;
    }
    return true;
}

vector<string> temp;
vector<vector<string>> ret;

void partitionBack(string &s, int startIndex) {

    if (startIndex > s.size())//原来这边边界也错误了 原来>=
        return;

    if (startIndex == s.size())// 这边原来写的==size-1都是最后一个 没办法 加入就返回了
    {
        ret.push_back(temp);
        return;
    }


    for (int i = startIndex; i < s.size(); ++i) {
        //注意改用引用就引用
        string temps = s.substr(startIndex, i - startIndex + 1);
        if (!isPalindrome(temps))//这边分割字符串我写错了应该是i-startIndex+1 我写成startindex+1；
            continue;
        temp.push_back(temps);

        partitionBack(s, i + 1);
        temp.pop_back();

    }


}

vector<vector<string>> partition(string s) {
    partitionBack(s, 0);
    return ret;


}














//给出的代码
//class Solution {
//private:
//    vector<vector<string>> result;
//    vector<string> path; // 放已经回⽂的⼦串
//    void backtracking (const string& s, int startIndex) {
//        // 如果起始位置已经⼤于s的⼤⼩，说明已经找到了⼀组分割⽅案了
//        if (startIndex >= s.size()) {
//            result.push_back(path);
//            return;
//        }
//        for (int i = startIndex; i < s.size(); i++) {
//            if (isPalindrome(s, startIndex, i)) { // 是回⽂⼦串
//                // 获取[startIndex,i]在s中的⼦串
//                string str = s.substr(startIndex, i - startIndex + 1);
//                path.push_back(str);
//                总结
//                这道题⽬在leetcode上是中等，但可以说是hard的题⽬了，但是代码其实就是按照模板的样⼦来的。
//                那么难究竟难在什么地⽅呢？
//                我列出如下⼏个难点：
//                切割问题可以抽象为组合问题
//                        如何模拟那些切割线
//                切割问题中递归如何终⽌
//                在递归循环中如何截取⼦串
//                如何判断回⽂
//                我们平时在做难题的时候，总结出来难究竟难在哪⾥也是⼀种需要锻炼的能⼒。
//                ⼀些同学可能遇到题⽬⽐较难，但是不知道题⽬难在哪⾥，反正就是很难。其实这样还是思维不够清
//                晰，这种总结的能⼒需要多接触多锻炼。
//                本题我相信很多同学主要卡在了第⼀个难点上：就是不知道如何切割，甚⾄知道要⽤回溯法，也不知道
//                如何⽤。也就是没有体会到按照求组合问题的套路就可以解决切割。
//                如果意识到这⼀点，算是重⼤突破了。接下来就可以对着模板照葫芦画瓢。
//                但接下来如何模拟切割线，如何终⽌，如何截取⼦串，其实都不好想，最后判断回⽂算是最简单的了。
//                除了这些难点，本题还有细节，例如：切割过的地⽅不能重复切割所以递归函数需要传⼊i + 1。
//            } else { // 不是回⽂，跳过
//                continue;
//            }
//            backtracking(s, i + 1); // 寻找i+1为起始位置的⼦串
//            path.pop_back(); // 回溯过程，弹出本次已经填在的⼦串
//        }
//    }
//    bool isPalindrome(const string& s, int start, int end) {
//        for (int i = start, j = end; i < j; i++, j--) {
//            if (s[i] != s[j]) {
//                return false;
//            }
//        }
//        return true;
//    }
//public:
//    vector<vector<string>> partition(string s) {
//        result.clear();
//        path.clear();
//        backtracking(s, 0);
//        return result;
//    }
//};
/*
 * 道题⽬在leetcode上是中等，但可以说是hard的题⽬了，但是代码其实就是按照模板的样⼦来的。
那么难究竟难在什么地⽅呢？
我列出如下⼏个难点：
切割问题可以抽象为组合问题
如何模拟那些切割线
切割问题中递归如何终⽌
在递归循环中如何截取⼦串
如何判断回⽂
我们平时在做难题的时候，总结出来难究竟难在哪⾥也是⼀种需要锻炼的能⼒。
⼀些同学可能遇到题⽬⽐较难，但是不知道题⽬难在哪⾥，反正就是很难。其实这样还是思维不够清
晰，这种总结的能⼒需要多接触多锻炼。
本题我相信很多同学主要卡在了第⼀个难点上：就是不知道如何切割，甚⾄知道要⽤回溯法，也不知道
如何⽤。也就是没有体会到按照求组合问题的套路就可以解决切割。
如果意识到这⼀点，算是重⼤突破了。接下来就可以对着模板照葫芦画瓢。
但接下来如何模拟切割线，如何终⽌，如何截取⼦串，其实都不好想，最后判断回⽂算是最简单的了。
除了这些难点，本题还有细节，例如：切割过的地⽅不能重复切割所以递归函数需要传⼊i + 1。
 } else { // 不是回⽂，跳过
 continue;
 }
 backtracking(s, i + 1); // 寻找i+1为起始位置的⼦串
 path.pop_back(); // 回溯过程，弹出本次已经填在的⼦串
 }
 }
 bool isPalindrome(const string& s, int start, int end) {
 for (int i = start, j = end; i < j; i++, j--) {
 if (s[i] != s[j]) {
 return false;
 }
 }
 return true;
 }
public:
 vector<vector<string>> partition(string s) {
 result.clear();
 path.clear();
 backtracking(s, 0);
 return result;
 }
};
所以本题应该是⼀个道hard题⽬了。
可能刷过这道题⽬的录友都没感受到⾃⼰原来克服了这么多难点，就把这道题⽬AC了，这应该叫做⽆招
胜有招，⼈码合⼀，哈哈哈。
当然，本题131.分割回⽂串还可以⽤暴⼒搜索⼀波，132.分割回⽂串II和1278.分割回⽂串III 爆搜就会超
时，需要使⽤动态规划了，我们会在动态规划系列中，详细讲解！
 *
 * */